Motion estimation, a technology widely used in image processing, determines a motion vector of an image corresponding to a similar image or an identical image within its adjacent frames. Most novel video encoding circuits, e.g., systems compatible to the H.26x or MPEG protocols, implement motion estimation to search for similarities between images from different video images, so as to achieve application functions, e.g., image compression.
Motion estimation is for finding a most appropriate motion vector, which represents a relative displacement of the same image block (i.e., a matching window) between two different frames. FIG. 1 shows a schematic diagram of a motion vector V in the prior art. The motion vector V represents a horizontal and vertical displacement vector (e.g., the motion vector V illustrated in FIG. 1) corresponding to an image block between a previous frame and a current frame.
The conventional image processing technology mainly uses block matching to find a motion vector. FIG. 2 shows a schematic diagram of motion estimation in the prior art, for matching a first frame 10 and a second frame 12, as shown. A predetermined matching window 100 having a size of, e.g., 16*16, 16*8, 8*16, 8*8, 8*4, 4*8 or 4*4 pixels, may be captured in the first frame 10. In FIG. 2, a matching window 100 having a size of 4*4 pixels is taken as an example.
A searching area 120 having a plurality of searching blocks, e.g., a searching block 1200a and 1200b illustrated in FIG. 2, is captured in the second frame 12. Each of the searching blocks has a size equal to that of the matching window 100. For example, referring to FIG. 2, the searching area 120 has a size of 8*10 pixels, and each of the searching blocks has a size of 4*4 pixels.
In the conventional motion estimation method, each of the searching blocks in the searching area is compared with the matching window 100 to obtain a difference corresponding to each of the searching blocks, and a smallest difference is found to locate a most similar searching block. Accordingly, a motion vector corresponding to the matching window 100 is determined based on the most similar searching block.
In a conventional full search algorithm, a matching window of a first image is compared with all possible searching blocks in a searching area of a second image one after another. Such full search algorithm has advantages of involving purely data processing programs and providing accurate matching results.
However, the conventional motion estimation method with the full search algorithm needs large amount of calculation resources, e.g., large amount of buffers for storing matching windows and image information of searching blocks during a matching process. In addition, comparing each possible searching block with the matching window one after another is rather complex and time-consuming. More particularly, time needed for calculation accordingly increases as the searching area becomes larger.
In another aspect, some conventional motion estimation methods do not use the full search algorithm that calculates a total difference on all searching blocks within a searching area. Instead, the total difference is calculated in a hopping manner, or the searching blocks are partially compared to obtain a total difference corresponding to the partially compared searching blocks. Consequently, although a motion estimation flow is accelerated, accuracy of a motion vector is deteriorated in reciprocation.
In order to solve the foregoing problem, a motion estimation method is provided to accelerate a motion estimation flow and save resources needed for calculation while maintaining the advantageous characteristics of the full search method without sacrificing the search accuracy.